1. Industrial Fields of the Invention
This invention relates to wavelet decomposition, especially to wavelet based video coding.
2. Related Art of the Invention
Besides DCT (Digital Cosine Transform) used in video coding, recently wavelet transform has been widely studied in video signal coding, since wavelet decomposition has spatio-frequency localization properties.
Wavelet transform is an alternative representation of image data. It decomposes an input raster image hierarchically in the vertical and horizontal direction, and forms many different multiresolution bands.
FIG. 1 illustrates an example, wavelet decomposition process, where an input image is decomposed into 13-band of wavelet coefficient, after 4 times of decomposition.
The three B4 bands are obtained from the first horizontal/vertical wavelet decomposition; the three B3 bands are obtained from the second decomposition; and so on. The lower bands B1, B2, and B3 contain much of the information of the original image, and the higher band B4 contributes detailed information to the original image.
FIG. 2 shows the real wavelet coefficients for Carphone Sequence, which is decomposed once by wavelet transform. It can be seen that there are some non-zero wavelet coefficients vertically distributed in the horizontal band, Hh, because of vertical edges in the original image, and some non-zero wavelet coefficients horizontally distributed in the vertical band, Hv, because of horizontal edges in the original image.
It has been known that if those non-zero wavelet coefficients in FIG. 2 could be represented and coded by using less bits, then the efficiency of the wavelet compression would be high.
In the paper "Wavelet Coefficients Scanning Methods for Video Coding", three scanning methods for wavelet coefficients were presented. One of them is called H.sub.-- Band/V.sub.-- Band/D.sub.-- Band Scan, which is the best scan among the three scanning methods.
FIG. 3 illustrates the scanning mechanism for H.sub.-- Band/V.sub.-- Band/D.sub.-- Band Scan.
Firstly wavelet coefficients are divided into three kinds of bands: horizontal band, vertical band, and diagonal band. Within the horizontal bands, B1h, B2h, B3h, and B4h, different number of wavelet coefficients are taken from different horizontal bands, one from B1h, 2.times.2 from B2h, 4.times.4 from B3h, 8.times.8 from B4h, and then they are grouped into a macro band with total number of 85 items. Finally the macro band is quantized and Huffman VLC coded.
FIG. 4 shows an example of three macro bands to be formed from horizontal bands, vertical bands, and diagonal bands, respectively. In the same paper "Wavelet Coefficients Scanning Methods for Video Coding", one dimension array will be further formed just by using normal raster scan no matter what band it is from. But it can be seen from FIG. 4 that in the horizontal band, there are a lot of cases where non-zero wavelet coefficients are vertically distributed, and inversely in the vertical band, there are a lot of cases where non-zero wavelet coefficients are horizontally distributed.
So if the situation could be considered, scanning wavelet coefficients vertically in horizontal bands and scanning wavelet coefficients horizontally in vertical bands, instead of raster scan, then the coding efficiency would be increased further.
In the same time, since a run-length Huffman VLC like entropy encoder will be applied to the array here, if non-zero wavelet coefficients in the array appear as the front of the array as much as possible, as well as to be small as much as possible, then less bits will be consumed.
The invention here is going to propose an adaptive scanning and differential pulse-code modulation (DPCM) process for the H.sub.-- Band/V.sub.-- Band/D.sub.-- Band Scan to improve its coding efficiency further, and the concept is also applicable to the similar cases where wavelet or subband decomposition is used and non-zero coefficients appear vertically in horizontal bands and horizontally in vertical bands.
Wavelet coding is composed of Wavelet Decomposition, Scanning, Quantizaition, as well as entropy coding. Besides choosing a better wavelet transform, scanning and quantising wavelet coefficients efficiently is also very important.
Edge information in an original image is often corresponding to non-zero wavelet coefficients after wavelet decomposition, and normally these coefficients are vertically distributed in horizontal bands and horizontally distributed in vertical bands. The invention is trying to make use of the phenomena to scan wavelet coefficients adaptively, so as to improve the coding efficiency of wavelet.
Further, it is shown that non-zero wavelet coefficients are distributed in different vertical line for different images, taken horizontal macro band as an example shown in FIG. 4. In order to use less bits to code them by Huffman VLC like entropy coder, those non-zero coefficients are needed to scan and put in the front of a 1-Dimension array as much as possible.
There are a lot of cases where wavelet coefficients in the same vertical line for horizontal band have the same value, at least have the same sign. So one dimension of DPCM coding could be used here for reducing the redundancy between neighbour coefficients.